package com.kim.datrie;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DoubleArrayTrie{
	private final char END_CHAR = '\000';

	private int pos = 1;

	private int count = 0;
	private int[] base;
	private int[] check;
	private char[] tail;
	private Map<Character, Integer> map = new HashMap();

	public DoubleArrayTrie(int size) {
	    this.base = new int[size];
	    this.check = new int[size];
	    this.tail = new char[size];
	    this.base[1] = 1;
	    this.map.put(Character.valueOf('\000'), Integer.valueOf(1));
	}

	private void extendArray() {
	    this.base = Arrays.copyOf(this.base, this.base.length * 2);
	    this.check = Arrays.copyOf(this.check, this.check.length * 2);
	}

	private void extendsTail() {
		this.tail = Arrays.copyOf(this.tail, this.tail.length * 2);
	}

	private int charCode(char c) {
		Integer code = (Integer)this.map.get(Character.valueOf(c));
		return code != null ? code.intValue() : compute(c, this.count++);
	}

	private int compute(char c, int count) {
	    if (!this.map.containsKey(Character.valueOf(c))) {
	      this.map.put(Character.valueOf(c), Integer.valueOf(count));
	    }
	    return count;
	}

	private int copy2TailArray(String s, int p) {
	    int pos = this.pos;
	    while (s.length() - p + 1 > this.tail.length - pos) {
	      extendsTail();
	    }
	    for (int i = p; i < s.length(); i++) {
	      this.tail[pos] = s.charAt(i);
	      pos++;
	    }
	    return pos;
	}

	private int check(Integer[] set) {
	    for (int i = 1; ; i++) {
	      boolean flag = true;
	      for (int j = 0; j < set.length; j++) {
	        int cur_p = i + set[j].intValue();
	        if (cur_p >= this.base.length)
	          extendArray();
	        if ((this.base[cur_p] != 0) || (this.check[cur_p] != 0)) {
	          flag = false;
	          break;
	        }
	      }
	      if (flag)
	        return i;
	    }
	}

	private ArrayList<Integer> childList(int p) {
	    ArrayList ret = new ArrayList();
	    for (int i = 1; (i <= this.map.size()) && 
	      (this.base[p] + i < this.check.length); i++)
	    {
	      if (this.check[(this.base[p] + i)] == p) {
	        ret.add(Integer.valueOf(i));
	      }
	    }
	    return ret;
	}

	private boolean tailContainString(int start, String s2) {
	    for (int i = 0; i < s2.length(); i++) {
	      if (s2.charAt(i) != this.tail[(i + start)])
	        return false;
	    }
	    return true;
	}

	private boolean tailMatchString(int start, String s2) {
	    s2 = s2 + '\000';
	    for (int i = 0; i < s2.length(); i++) {
	      if (s2.charAt(i) != this.tail[(i + start)])
	        return false;
	    }
	    return true;
	}

  public void insert(List<String> s) {
    for (String each : s)
    {
      insert(each);
    }
  }

  public void insert(String s){
	  s = s + '\000';
	  int pre_p = 1;

	  for (int i = 0; i < s.length(); i++){
      int cur_p = this.base[pre_p] + charCode(s.charAt(i));

      if (cur_p >= this.base.length) {
        extendArray();
      }
      if ((this.base[cur_p] == 0) && (this.check[cur_p] == 0)) {
        this.base[cur_p] = (-this.pos);
        this.check[cur_p] = pre_p;
        this.pos = copy2TailArray(s, i + 1);
        break;
      }

      if ((this.base[cur_p] > 0) && (this.check[cur_p] == pre_p)) {
        pre_p = cur_p;
      }
      else if ((this.base[cur_p] < 0) && (this.check[cur_p] == pre_p)) {
        int head = -this.base[cur_p];

        if ((i + 1 >= s.length()) || ((s.charAt(i + 1) == 0) && (this.tail[head] == 0)))
        {
          break;
        }
        if (this.tail[head] == s.charAt(i + 1)) {
          int avail_base = check(new Integer[] { Integer.valueOf(charCode(s.charAt(i + 1))) });
          this.base[cur_p] = avail_base;
          this.check[(avail_base + charCode(s.charAt(i + 1)))] = cur_p;
          this.base[(avail_base + charCode(s.charAt(i + 1)))] = (-(head + 1));
          pre_p = cur_p;
        }
        else
        {
          int avail_base = check(new Integer[] { Integer.valueOf(charCode(s.charAt(i + 1))), Integer.valueOf(charCode(this.tail[head])) });
          this.base[cur_p] = avail_base;
          this.check[(avail_base + charCode(this.tail[head]))] = cur_p;
          this.check[(avail_base + charCode(s.charAt(i + 1)))] = cur_p;

          if (this.tail[head] == 0)
            this.base[(avail_base + charCode(this.tail[head]))] = 0;
          else
            this.base[(avail_base + charCode(this.tail[head]))] = (-(head + 1));
          if (s.charAt(i + 1) == 0)
            this.base[(avail_base + charCode(s.charAt(i + 1)))] = 0;
          else
            this.base[(avail_base + charCode(s.charAt(i + 1)))] = (-this.pos);
          this.pos = copy2TailArray(s, i + 2);
          break;
        }

      }
      else if (this.check[cur_p] != pre_p) {
        ArrayList list1 = childList(pre_p);

        ArrayList list = null;

        int toBeAdjust = pre_p;
        list = list1;

        int origin_base = this.base[toBeAdjust];
        list.add(Integer.valueOf(charCode(s.charAt(i))));
        int avail_base = check((Integer[])list.toArray(new Integer[list.size()]));
        list.remove(list.size() - 1);
        this.base[toBeAdjust] = avail_base;
        for (int j = 0; j < list.size(); j++)
        {
          int tmp1 = origin_base + ((Integer)list.get(j)).intValue();
          int tmp2 = avail_base + ((Integer)list.get(j)).intValue();
          this.base[tmp2] = this.base[tmp1];
          this.check[tmp2] = this.check[tmp1];

          if (this.base[tmp1] > 0) {
            ArrayList subsequence = childList(tmp1);
            for (int k = 0; k < subsequence.size(); k++) {
              this.check[(this.base[tmp1] + ((Integer)subsequence.get(k)).intValue())] = tmp2;
            }
          }
          this.base[tmp1] = 0;
          this.check[tmp1] = 0;
        }

        cur_p = this.base[pre_p] + charCode(s.charAt(i));
        if (s.charAt(i) == 0)
          this.base[cur_p] = 0;
        else
          this.base[cur_p] = (-this.pos);
        this.check[cur_p] = pre_p;
        this.pos = copy2TailArray(s, i + 1);
        break;
      }
    }
  }

  public boolean exists(String word) {
    int pre_p = 1;
    int cur_p = 0;
    for (int i = 0; i < word.length(); i++) {
      cur_p = this.base[pre_p] + charCode(word.charAt(i));
      if ((cur_p < this.check.length) && (this.check[cur_p] != pre_p))
        return false;
      if ((cur_p < this.base.length) && (this.base[cur_p] < 0)) {
        if (tailMatchString(-this.base[cur_p], word.substring(i + 1)))
          return true;
        return false;
      }
      pre_p = cur_p;
    }
    if ((cur_p < this.base.length) && (this.base[cur_p] + charCode('\000') < this.check.length) && 
      (this.check[
      (this.base[cur_p] + 
      charCode('\000'))] == 
      cur_p))
      return true;
    return false;
  }

  private int find(String word) {
    int pre_p = 1;
    int cur_p = 0;
    for (int i = 0; i < word.length(); i++)
    {
      cur_p = this.base[pre_p] + charCode(word.charAt(i));
      if ((cur_p < this.check.length) && (this.check[cur_p] != pre_p)) {
        return -1;
      }
      if ((cur_p < this.base.length) && (this.base[cur_p] < 0)) {
        if (tailContainString(-this.base[cur_p], word.substring(i + 1))) {
          return cur_p;
        }
        return -1;
      }
      pre_p = cur_p;
    }
    return cur_p;
  }

  public boolean prefix(String word) {
    int p = find(word);
    return (p < this.base.length) && (p != -1);
  }
}